/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: test_heap.c 36 2009-11-02 15:06:50Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

#include <CUnit/Basic.h>

#include <../src/heap.h>
#include <../src/function_prototypes.h>

#include "test_helpers.h"
#include "test_heap.h"

Heap *heap;

int
init_test_heap_suite ()
{
  if ((heap = heap_create (&comp_int)) == NULL)
    return 1;
  else
    return 0;
}

int
clean_test_heap_suite ()
{
  heap_destroy (heap, &dest_int, 1);

  return 0;
}

void
test_heap_insert_find_extract ()
{
  int *i, *j, x;

  for (x = 0; x < 10; x++)
    {
      i = create_int (x);
      CU_ASSERT (heap_insert (heap, i) == 1);
      CU_ASSERT (heap_size (heap) == x + 1);
    }

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 0);
  CU_ASSERT (heap_size (heap) == 9);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 1);
  CU_ASSERT (heap_size (heap) == 8);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 2);
  CU_ASSERT (heap_size (heap) == 7);
  free (i);

  for (x = 0; x < 10; x++)
    {
      i = create_int (x);
      CU_ASSERT (heap_insert (heap, i) == 1);
      CU_ASSERT (heap_size (heap) == 7 + x + 1);
    }

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 0);
  CU_ASSERT (heap_size (heap) == 16);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 1);
  CU_ASSERT (heap_size (heap) == 15);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 2);
  CU_ASSERT (heap_size (heap) == 14);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 3);
  CU_ASSERT (heap_size (heap) == 13);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 3);
  CU_ASSERT (heap_size (heap) == 12);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 4);
  CU_ASSERT (heap_size (heap) == 11);
  free (i);

  CU_ASSERT ((j = heap_find_min (heap)) != NULL);
  CU_ASSERT ((i = heap_extract_min (heap)) != NULL);
  CU_ASSERT (i == j);
  CU_ASSERT (*i == 4);
  CU_ASSERT (heap_size (heap) == 10);
  free (i);

}

int
make_heap_suite (CU_pSuite s)
{
  s = CU_add_suite ("Test Heap Suite", 
		    init_test_heap_suite, 
		    clean_test_heap_suite);
  if (s == NULL)
    {
      return CU_get_error();
    }

  if (CU_add_test (s, "test_heap_insert_find_extract", 
		   test_heap_insert_find_extract) == NULL)
    {
      return CU_get_error ();
    }

  return CU_get_error();
}


